`
https://leetcode.cn/problems/maximum-number-of-alloys/
`

/**
 * @param {number} n
 * @param {number} k
 * @param {number} budget
 * @param {number[][]} composition
 * @param {number[]} stock
 * @param {number[]} cost
 * @return {number}
 */
var maxNumberOfAlloys = function (n, k, budget, composition, stock, cost) {
  let res = 0
  // 最多能制造多少份合金
  const mx = Math.min(...stock) + budget
  // 遍历每类金属，计算总花费。如果总花费超过 budget，则无法制造 num 份合金，否则可以制造
  for (const comp of composition) {
    const check = (num) => {
      let money = 0
      for (let i = 0; i < n; i++) {
        if (stock[i] < comp[i] * num) {
          money += (comp[i] * num - stock[i]) * cost[i]
          if (money > budget) return false
        }
      }
      return true
    }

    let left = res, right = mx + 1
    while (left + 1 < right) {
      const mid = left + Math.floor((right - left) / 2)
      if (check(mid)) {
        left = mid
      } else {
        right = mid
      }
    }
    res = left
  }
  return res
};